home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / BYacc-CW 1.9 / mkpar.c < prev    next >
Text File  |  1995-05-20  |  6KB  |  345 lines
  1.  
  2. #include "defs.h"
  3.  
  4. action **parser;
  5. int SRtotal;
  6. int RRtotal;
  7. short *SRconflicts;
  8. short *RRconflicts;
  9. short *defred;
  10. short *rules_used;
  11. short nunused;
  12. short final_state;
  13.  
  14. static int SRcount;
  15. static int RRcount;
  16.  
  17. extern action *parse_actions();
  18. extern action *get_shifts();
  19. extern action *add_reductions();
  20. extern action *add_reduce();
  21.  
  22.  
  23.  
  24. static action *parse_actions(register int stateno)
  25. {
  26.     register action *actions;
  27.  
  28.     actions = get_shifts(stateno);
  29.     actions = add_reductions(stateno, actions);
  30.     return (actions);
  31. }
  32.  
  33.  
  34. static action *get_shifts(int stateno)
  35. {
  36.     register action *actions, *temp;
  37.     register shifts *sp;
  38.     register short *to_state;
  39.     register int i, k;
  40.     register int symbol;
  41.  
  42.     actions = 0;
  43.     sp = shift_table[stateno];
  44.     if (sp)
  45.     {
  46.     to_state = sp->shift;
  47.     for (i = sp->nshifts - 1; i >= 0; i--)
  48.     {
  49.         k = to_state[i];
  50.         symbol = accessing_symbol[k];
  51.         if (ISTOKEN(symbol))
  52.         {
  53.         temp = NEW(action);
  54.         temp->next = actions;
  55.         temp->symbol = symbol;
  56.         temp->number = k;
  57.         temp->prec = symbol_prec[symbol];
  58.         temp->action_code = SHIFT;
  59.         temp->assoc = symbol_assoc[symbol];
  60.         actions = temp;
  61.         }
  62.     }
  63.     }
  64.     return (actions);
  65. }
  66.  
  67. static action *add_reductions(int stateno, register action *actions)
  68. {
  69.     register int i, j, m, n;
  70.     register int ruleno, tokensetsize;
  71.     register unsigned *rowp;
  72.  
  73.     tokensetsize = WORDSIZE(ntokens);
  74.     m = lookaheads[stateno];
  75.     n = lookaheads[stateno + 1];
  76.     for (i = m; i < n; i++)
  77.     {
  78.     ruleno = LAruleno[i];
  79.     rowp = LA + i * tokensetsize;
  80.     for (j = ntokens - 1; j >= 0; j--)
  81.     {
  82.         if (BIT(rowp, j))
  83.         actions = add_reduce(actions, ruleno, j);
  84.     }
  85.     }
  86.     return (actions);
  87. }
  88.  
  89.  
  90. static action *add_reduce(register action *actions, register int ruleno, register int symbol)
  91. {
  92.     register action *temp, *prev, *next;
  93.  
  94.     prev = 0;
  95.     for (next = actions; next && next->symbol < symbol; next = next->next)
  96.     prev = next;
  97.  
  98.     while (next && next->symbol == symbol && next->action_code == SHIFT)
  99.     {
  100.     prev = next;
  101.     next = next->next;
  102.     }
  103.  
  104.     while (next && next->symbol == symbol &&
  105.         next->action_code == REDUCE && next->number < ruleno)
  106.     {
  107.     prev = next;
  108.     next = next->next;
  109.     }
  110.  
  111.     temp = NEW(action);
  112.     temp->next = next;
  113.     temp->symbol = symbol;
  114.     temp->number = ruleno;
  115.     temp->prec = rprec[ruleno];
  116.     temp->action_code = REDUCE;
  117.     temp->assoc = rassoc[ruleno];
  118.  
  119.     if (prev)
  120.     prev->next = temp;
  121.     else
  122.     actions = temp;
  123.  
  124.     return (actions);
  125. }
  126.  
  127.  
  128. static void find_final_state(void)
  129. {
  130.     register int goal, i;
  131.     register short *to_state;
  132.     register shifts *p;
  133.  
  134.     p = shift_table[0];
  135.     to_state = p->shift;
  136.     goal = ritem[1];
  137.     for (i = p->nshifts - 1; i >= 0; --i)
  138.     {
  139.     final_state = to_state[i];
  140.     if (accessing_symbol[final_state] == goal) break;
  141.     }
  142. }
  143.  
  144.  
  145. static void unused_rules(void)
  146. {
  147.     register int i;
  148.     register action *p;
  149.  
  150.     rules_used = (short *) MALLOC(nrules*sizeof(short));
  151.     if (rules_used == 0) no_space();
  152.  
  153.     for (i = 0; i < nrules; ++i)
  154.     rules_used[i] = 0;
  155.  
  156.     for (i = 0; i < nstates; ++i)
  157.     {
  158.     for (p = parser[i]; p; p = p->next)
  159.     {
  160.         if (p->action_code == REDUCE && p->suppressed == 0)
  161.         rules_used[p->number] = 1;
  162.     }
  163.     }
  164.  
  165.     nunused = 0;
  166.     for (i = 3; i < nrules; ++i)
  167.     if (!rules_used[i]) ++nunused;
  168.  
  169.     if (nunused)
  170.     if (nunused == 1)
  171.         fprintf(stderr, "%s: 1 rule never reduced\n", myname);
  172.     else
  173.         fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
  174. }
  175.  
  176.  
  177. static void remove_conflicts(void)
  178. {
  179.     register int i;
  180.     register int symbol;
  181.     register action *p, *pref;
  182.  
  183.     SRtotal = 0;
  184.     RRtotal = 0;
  185.     SRconflicts = NEW2(nstates, short);
  186.     RRconflicts = NEW2(nstates, short);
  187.     for (i = 0; i < nstates; i++)
  188.     {
  189.     SRcount = 0;
  190.     RRcount = 0;
  191.     symbol = -1;
  192.     for (p = parser[i]; p; p = p->next)
  193.     {
  194.         if (p->symbol != symbol)
  195.         {
  196.         pref = p;
  197.         symbol = p->symbol;
  198.         }
  199.         else if (i == final_state && symbol == 0)
  200.         {
  201.         SRcount++;
  202.         p->suppressed = 1;
  203.         }
  204.         else if (pref->action_code == SHIFT)
  205.         {
  206.         if (pref->prec > 0 && p->prec > 0)
  207.         {
  208.             if (pref->prec < p->prec)
  209.             {
  210.             pref->suppressed = 2;
  211.             pref = p;
  212.             }
  213.             else if (pref->prec > p->prec)
  214.             {
  215.             p->suppressed = 2;
  216.             }
  217.             else if (pref->assoc == LEFT)
  218.             {
  219.             pref->suppressed = 2;
  220.             pref = p;
  221.             }
  222.             else if (pref->assoc == RIGHT)
  223.             {
  224.             p->suppressed = 2;
  225.             }
  226.             else
  227.             {
  228.             pref->suppressed = 2;
  229.             p->suppressed = 2;
  230.             }
  231.         }
  232.         else
  233.         {
  234.             SRcount++;
  235.             p->suppressed = 1;
  236.         }
  237.         }
  238.         else
  239.         {
  240.         RRcount++;
  241.         p->suppressed = 1;
  242.         }
  243.     }
  244.     SRtotal += SRcount;
  245.     RRtotal += RRcount;
  246.     SRconflicts[i] = SRcount;
  247.     RRconflicts[i] = RRcount;
  248.     }
  249. }
  250.  
  251.  
  252. static void total_conflicts(void)
  253. {
  254.     fprintf(stderr, "%s: ", myname);
  255.     if (SRtotal == 1)
  256.     fprintf(stderr, "1 shift/reduce conflict");
  257.     else if (SRtotal > 1)
  258.     fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
  259.  
  260.     if (SRtotal && RRtotal)
  261.     fprintf(stderr, ", ");
  262.  
  263.     if (RRtotal == 1)
  264.     fprintf(stderr, "1 reduce/reduce conflict");
  265.     else if (RRtotal > 1)
  266.     fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
  267.  
  268.     fprintf(stderr, ".\n");
  269. }
  270.  
  271.  
  272. static int sole_reduction(int stateno)
  273. {
  274.     register int count, ruleno;
  275.     register action *p;
  276.  
  277.     count = 0;
  278.     ruleno = 0; 
  279.     for (p = parser[stateno]; p; p = p->next)
  280.     {
  281.     if (p->action_code == SHIFT && p->suppressed == 0)
  282.         return (0);
  283.     else if (p->action_code == REDUCE && p->suppressed == 0)
  284.     {
  285.         if (ruleno > 0 && p->number != ruleno)
  286.         return (0);
  287.         if (p->symbol != 1)
  288.         ++count;
  289.         ruleno = p->number;
  290.     }
  291.     }
  292.  
  293.     if (count == 0)
  294.     return (0);
  295.     return (ruleno);
  296. }
  297.  
  298.  
  299. static void defreds(void)
  300. {
  301.     register int i;
  302.  
  303.     defred = NEW2(nstates, short);
  304.     for (i = 0; i < nstates; i++)
  305.     defred[i] = sole_reduction(i);
  306. }
  307.  
  308. static void free_action_row(register action *p)
  309. {
  310.   register action *q;
  311.  
  312.   while (p)
  313.     {
  314.       q = p->next;
  315.       FREE(p);
  316.       p = q;
  317.     }
  318. }
  319.  
  320. void free_parser(void)
  321. {
  322.   register int i;
  323.  
  324.   for (i = 0; i < nstates; i++)
  325.     free_action_row(parser[i]);
  326.  
  327.   FREE(parser);
  328. }
  329.  
  330. void make_parser(void)
  331. {
  332.     register int i;
  333.  
  334.     parser = NEW2(nstates, action *);
  335.     for (i = 0; i < nstates; i++)
  336.     parser[i] = parse_actions(i);
  337.  
  338.     find_final_state();
  339.     remove_conflicts();
  340.     unused_rules();
  341.     if (SRtotal + RRtotal > 0) total_conflicts();
  342.     defreds();
  343. }
  344.  
  345.